class Solution(object):
    def integerReplacement(self, n):
        def traverse(i):
            if i==1: return 0
            if i%2==0:
                return traverse(i//2)+1
            else:
                return min(traverse(i+1),traverse(i-1))+1
        return traverse(n)

print(Solution().integerReplacement(111111111))